The present invention relates to a method and apparatus for error correction and, more particularly, to an error correction method and apparatus which executes a syndrome operation without deinterleaving information data, which has been interleaved, and performs error correction.
A-syndrome operation of error correction processings for the CD-ROM (Compact Disc-Read Only Memory) is described with reference to FIGS. 4 to 7. FIG. 4 is a diagram showing a data format of one sector of the CD-ROM, which is represented on the basis of audio data (L and R stereo signals). L-CH denotes data of the left channel and R-CH denotes data of the right channel. xe2x80x9cLxe2x80x9d denotes a Least Significant Bit (LSB) and xe2x80x9cMxe2x80x9d denotes a Most Significant Bit (MSB). Upper three lines denoted by reference numeral 1 show a synchronous pattern representing one sector, and the next 585 lines below numeral 1, denoted by numeral 2, show the pattern of data.
FIG. 5 is a map which is formed by selecting only less significant bytes in the data of one sector shown in FIG. 4. The plane which is composed of only less significant bytes is referred to as a least significant plane. Further, a plane which is composed of only more significant bytes is referred to as a most significant plane. The upper 24 lines denoted by numeral 4 show the header except the synchronous pattern and user data. The next two lines denoted by numeral 5 show P parity and the subsequent two lines denoted by numeral 6 show Q parity. The most significant plane has the same form as that of the least significant plane. The respective planes are subjected to the same ECC (Error Check and Correct). In addition, in the case of the CD-ROM, the ECC is performed for two codeword sequences, i.e., P sequence and Q sequence.
FIGS. 6 and 7 show the data of Q sequence shown in FIG. 5, which are rearranged in the direction of row (j). It can be seen that code sequences each having a code length n composed of 45 bytes (j=0-44) are arranged in 26 (i=0-25) rows. When i=0, the syndrome operation is executed with reading data every xe2x80x9c44xe2x80x9d, i.e., xe2x80x9c0xe2x80x9d, xe2x80x9c44xe2x80x9d, xe2x80x9c88xe2x80x9d, . . . . Similarly when i=1, the operation is executed with reading data every xe2x80x9c44xe2x80x9d, i.e., xe2x80x9c43xe2x80x9d, xe2x80x9c87xe2x80x9d, xe2x80x9c131xe2x80x9d, . . . . This is given by the following expression:
Q=43i+44j mod 1118 (i =0-25, j=0-44)xe2x80x83xe2x80x83(Expression 13)
Japanese Published Patent Application No. Hei.5-12814 shows a method of executing syndrome operations in parallel and performing(error correction, without putting the data of Q sequence which have been rearranged in byte units, i.e., interleaved, in their original places, i.e., without deinterleaving the data. In this method, with utilizing the property that ECCs (Error-Correcting Codes) for the most significant plane and the least significant plane are irrelevant to each other, i.e., independent, 1 byte of data is respectively read on the most significant plane and the least significant plane (referred to as page0 and page1 in this Published Application) successively from the first data of codeword sequences arranged in the direction of row (j) among data stored at contiguous addresses in a buffer memory, i.e., 2 bytes of data are read, and the operations are executed in parallel by two syndrome operation circuits which are provided so as to respectively correspond to the most significant plane and the least significant plane.
As described above, the prior art error correction apparatus reads 1 byte of data on the most significant plane and the least significant plane, respectively, i.e., reads 2 bytes of data in total, successively from the first data of the interleaved data in each codeword sequence, and executes the operations in the two syndrome operation circuits in parallel, thereby increasing the speed of the operations. However, it is difficult to increase the parallelism of the operation to further increase the speed with this error correction apparatus.
In order to more specifically describe this, assume that in addition to 2 bytes of data as in the prior art, 2 bytes of data at the subsequent addresses are further read. In this case, xe2x80x9c0001Lxe2x80x9d and xe2x80x9c0001Mxe2x80x9d are read in addition to xe2x80x9c0000Lxe2x80x9d and xe2x80x9c0000Mxe2x80x9d, i.e., 4 bytes of data are read in total. Here, xe2x80x9c0000Lxe2x80x9d and xe2x80x9c0000Mxe2x80x9d correspond to xe2x80x9c0xe2x80x9d shown in FIG. 6 and are the first (j=0) data in the codeword sequence of i=0. On the other hand, xe2x80x9c0001Lxe2x80x9d and xe2x80x9c0001Mxe2x80x9d correspond to xe2x80x9c1xe2x80x9d shown in FIG. 6 and are the second (j=1) data in the codeword sequence of i=25.
More specifically, since the order in which xe2x80x9c0000Lxe2x80x9d and xe2x80x9c0000Mxe2x80x9d are subjected to the operations is different from the order in which xe2x80x9c0001Lxe2x80x9d and xe2x80x9c0001Mxe2x80x9d are subjected to the operation, their operations cannot be performed in parallel. In addition, when the operation is started from data halfway through the codeword sequence like xe2x80x9c0001Lxe2x80x9d and xe2x80x9c0001Mxe2x80x9d, an error occurs in the syndrome operation result. Thus, it is required to put the interleaved data in the their original places, i.e., deinterleave the data, and then execute the syndrome operation. Accordingly, the parallel operation of the syndrome cannot be performed by merely increasing the number of bytes of read data.
It is an object of the present invention to provide an error correction method and apparatus for performing a high-speed operation, which can directly execute the operation, without deinterleaving plural bytes of data which are read according to the parallelism of the syndrome operation circuits.
Other objects and advantages of the present invention will become apparent from the detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the spirit and scope of the invention will be apparent to those of skill in the art from the detailed description.
A method for error correction according to a 1st aspect of the present invention comprises a first step of repeating a product-sum operation using (nxe2x88x92s) codewords from an s-th codeword (1xe2x89xa6Sxe2x89xa6nxe2x88x921) halfway through a codeword sequence of a code length n (n is a positive integer) composed of 0th to (n-1)-th codewords, which is taken as an operation start data, to the (n-1)-th codeword, and obtaining a first partial syndrome polynomial; a second step of multiplying the first partial syndrome polynomial by index compensating coefficients to obtain a second partial syndrome polynomial; and a third step of repeating a product-sum operation using s pieces of codewords from the 0th codeword which is a first codeword in the codeword sequence, taken as an operation restart data, to a (sxe2x88x921)-th codeword on the basis of the second partial syndrome polynomial and obtaining a syndrome polynomial of the codeword sequence. Therefore, the operation can be performed directly without deinterleaving the read data, whereby the high-speed syndrome operation can be realized.
According to a 2nd aspect of the present invention, in the error correction method of the 1st aspect, when the 0th codeword which is the first codeword of the codeword sequence is taken as the operation start data, the product-sum operation is repeatedly performed using n pieces of codewords from the 0th codeword to the (nxe2x88x921)-th codeword to obtain the syndrome polynomial of the code sequence. Therefore, the high-speed syndrome operation can be performed.
According to a 3rd aspect of the present invention, in the error correction method of the 1st aspect, when the 0th codeword which is the first codeword in the code sequence is taken as the operation start data, the first and second steps are executed to obtain the syndrome polynomial of the codeword sequence. Therefore, the syndrome operation having a high parallelism can be executed.
An apparatus for error correction according to a 4th aspect of the present invention comprises syndrome operation means for repeating a cycle in which a syndrome operation is started taking an s-th codeword (1xe2x89xa6sxe2x89xa6nxe2x88x921) in a codeword sequence i (i is an integer which is 0 or more) of a codeword length n (n is a positive integer) composed of 0th to (nxe2x88x921)-th codewords as an operation start data, and when the syndrome operation for the s-th codeword is completed, a syndrome operation is performed for a polynomial which is obtained by adding a result of the syndrome operation and a next (s+1)-th codeword, n times, thereby obtaining a syndrome polynomial composed of n terms. The syndrome operation means comprises: addition means for adding a result of a syndrome operation of a p-th (1xe2x89xa6pxe2x89xa6nxe2x88x921) cycle and a codeword of a (p+1)-th cycle to obtain a polynomial composed of(p+1) terms; first Galois field multiplication means for multiplying each term of the polynomial from the addition means by an element xcex1i xcex1xcex3 of a Galois field to obtain a syndrome polynomial of the (p+1)-th cycle; operation result storage means for containing the syndrome polynomial of the (p+1)-th cycle from the first Galois field multiplication means as an operation interim result; second Galois field multiplication means for multiplying the operation interim result from the operation result storage means by index compensating coefficients, and outputting a partial syndrome; and index compensated output selecting means for selecting one of the operation interim result from the operation result storage means and the partial syndrome from the second Galois field multiplication means, and outputting selected one to the addition means as a result of a syndrome operation in the (p+1)-th cycle, and the index compensated output selecting means selects the partial syndrome from the second Galois field multiplication means in a (nxe2x88x92s)-th cycle in which a syndrome operation of a last codeword in the codeword sequence is performed. Therefore, the operation can be performed directly without deinterleaving the read data, whereby the high-speed syndrome operation can be executed.
According to a 5th aspect of the present invention, in the error correction apparatus of the 4th aspect, a plurality of the syndrome operation means are included, and codewords of plural codeword sequences are respectively input to the syndrome operation means for corresponding codeword sequences, to perform syndrome polynomial operations for the plural codeword sequences in parallel. Therefore, the syndrome operation realizing a high parallelism can be performed, whereby the operation can be executed at high speed.
According to a 6th aspect of the present invention, the error correction apparatus of the 4th or 5th aspect comprises counter means for generating an index compensation cycle signal of a codeword sequence which is subjected to index compensation first among the plural codeword sequences; and delay means for generating h pieces of delay signals corresponding to the number h (h is a positive integer) of the plural syndrome operation means, said delay signals being delayed with respect to the index compensation cycle signal successively by k cycles (k is a positive integer) based on the index compensation cycle signal, and the delay means outputs the delay signals to the index compensated output selecting means included in each of the syndrome operation means as selection signals, respectively, thereby executing the index compensation for the operation interim result in each of the syndrome operation means with delay of k cycles each. Therefore, the index compensation for each codeword sequence can be automatically performed and the syndrome operation can have a high parallelism, whereby the operation can be performed at high speed.